package com.practice.niuke.new_direct_practice.class13;

/**
 * 给定一棵二叉树的头节点head，请返回二叉树的最小高度。
 * 要求：时间复杂度O(N)，额外空间复杂度O(1)
 */
public class Code05_MinHeight {

    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int x) {
            val = x;
        }
    }

    // ******************************方法一：二叉树的DP套路**********************************

    /**
     * 二叉树递归套路的主函数（调用递归函数）
     *
     * @param head 头节点
     * @return int
     */
    public static int minHeight(Node head) {
        if (head == null){
            return 0;
        }
        return process(head);
    }

    /**
     * 二叉树的递归套路的递归函数
     *
     * @param head head
     * @return int
     */
    public static int process(Node head) {
        if (head.left == null && head.right == null){
            return 1;
        }
        int lH = Integer.MAX_VALUE;
        // 左树上的最小高度
        if (head.left != null){
            lH = process(head.left);
        }
        int rH = Integer.MAX_VALUE;
        // 右树上的最小高度
        if (head.right != null){
            rH = process(head.right);
        }
        return Math.min(rH, lH) + 1;
    }


    // ******************************方法二：Morris遍历**********************************

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x) {
            val = x;
        }
    }

    public static int minDepth1(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head, 1);
    }

    // 返回head这棵树，最小高度，head在level层
    public static int process(TreeNode head, int level) {
        if (head.left == null && head.right == null) {
            return level;
        }
        int ans = Integer.MAX_VALUE;
        if (head.left != null) {
            ans = Math.min(process(head.left, level + 1), ans);
        }
        if (head.right != null) {
            ans = Math.min(process(head.right, level + 1), ans);
        }
        return ans;
    }

    // 根据morris遍历改写（TODO：Morris遍历的解法）
    public static int minDepth2(TreeNode head) {
        if (head == null) {
            return 0;
        }
        TreeNode cur = head;
        TreeNode mostRight = null;
        int curLevel = 0;
        int minHeight = Integer.MAX_VALUE;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                int leftHeight = 1;
                while (mostRight.right != null && mostRight.right != cur) {
                    leftHeight++;
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) { // 第一次到达
                    curLevel++;
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // 第二次到达
                    if (mostRight.left == null) {
                        // 发现所有叶节点高度的时机
                        minHeight = Math.min(minHeight, curLevel);
                    }
                    curLevel -= leftHeight;
                    mostRight.right = null;
                }
            } else { // 只有一次到达
                curLevel++;
            }
            cur = cur.right;
        }
        int finalRight = 1;
        cur = head;
        while (cur.right != null) {
            finalRight++;
            cur = cur.right;
        }
        if (cur.left == null && cur.right == null) {
            // 如果整棵树最右节点是叶节点，参与到叶节点高度的更新上面去
            minHeight = Math.min(minHeight, finalRight);
        }
        return minHeight;
    }

    // morris遍历，没有被调用，只是根据该方法改写出上面的方法
    public static void morris(TreeNode head) {
        if (head == null) {
            return;
        }
        TreeNode cur1 = head;
        TreeNode cur2 = null;
        while (cur1 != null) {
            cur2 = cur1.left;
            if (cur2 != null) {
                while (cur2.right != null && cur2.right != cur1) {
                    cur2 = cur2.right;
                }
                if (cur2.right == null) {
                    cur2.right = cur1;
                    cur1 = cur1.left;
                    continue;
                } else {
                    cur2.right = null;
                }
            }
            cur1 = cur1.right;
        }
    }

}
